

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#include "common/utils.hpp"

// 自底向上 层序遍历
// 自上向下层序遍历后翻转 vector 即可
std::vector<std::vector<int>> levelOrder2(TreeNode* root) {
    std::queue<TreeNode*> treeNodeQueue;
    
    if (root != nullptr) {
        treeNodeQueue.push(root);
    }
    
    std::vector<std::vector<int>> result;
    while (!treeNodeQueue.empty())
    {
        std::vector<int> vec;
        // 需要先记录这一层有几个节点
        int size = treeNodeQueue.size();
        for (int i{}; i < size; i++) {
            TreeNode* node = treeNodeQueue.front();
            vec.push_back(node->val);
            treeNodeQueue.pop();
            if (node->left) treeNodeQueue.push(node->left);
            if (node->right) treeNodeQueue.push(node->right);
        }
        result.push_back(vec);
    }

    std::reverse(result.begin(), result.end());
    return result;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<std::vector<int>> res = levelOrder2(commonRoot);
    std::cout << "levelOrder2: \n";
    for (int i{}; i < res.size(); i++) {
        printVector(res[i]);
    }
}